#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int rotate = 0;
        int size = nums.size();
        for(int i = 1; i < size; ++i){
            if(nums[i-1] > nums[i]){
                rotate = i;
                break;
            }
        }
        int low = rotate, high = rotate+size-1;
        cout << low << " " << high << endl;
        while(low <= high){
            int mid = (low+high)/2;
            cout << nums[mid%size] << endl;
            if(nums[mid%size] == target)
                return true;
            else if(nums[mid%size] < target)
                low = mid+1;
            else
                high = mid-1;
        }
        return false;
    }
};

int main(){
    int arr[] = {4, 5, 6, 7, 0, 1, 2};
    int target = 5;
    int length = sizeof(arr)/sizeof(int);
    vector<int> vec(arr, arr+length);
    Solution solution;
    cout << (solution.search(vec, target) ? "true" : "false") << endl;
    return 0;
}